
#include "binary_heap.h"

#include <stdlib.h>

#define ERR_INIT "error initializing heap\n"
#define ERR_ALREADY_INIT "heap already initialized\n"
#define ERR_EXPAND "error expanding heap\n"
#define ERR_REDUCE "error reducing heap\n"
#define ERR_NO_MIN "error extracting minimum: Heap has no elements\n"
#define INDENTATION "  "

/* shrink / expand heap by counts of 5 */
const size_t ALLOC_SIZE = 5;
/* 8 Bytes for a 64 bit pointer */
const size_t ALLOC_BYTES = 8;

/* points to the heap. */
BTREE **heap;

/* holds the heaps size */
int heap_size;

/* holds the heaps usage */
int heap_usage;

extern void heap_init(void)
{
    if (heap != NULL)
    {
        printf(ERR_ALREADY_INIT);
        return;
    }
    heap = malloc(ALLOC_SIZE*ALLOC_BYTES);

    if (heap == NULL)
    {
        printf(ERR_INIT);
        exit(EXIT_FAILURE);
    }

    heap_size = ALLOC_SIZE;
    heap_usage = 0;
}

extern void heap_destroy(void)
{
    if (heap == NULL)
    {
        printf(ERR_ALREADY_INIT);
    }
    free(heap);
    heap = NULL;
}

extern void heap_insert(BTREE *element)
{
    int parent_index;
    int insert_index;
    BTREE *swap_helper;

    check_more_memory();

    /* Insert into first free slot */
    insert_index = heap_usage;
    heap[heap_usage] = element;
    parent_index = get_parent_index(insert_index);

    while (parent_index != -1 && (heap[insert_index]->value < heap[parent_index]->value))
    {
        swap_helper = heap[parent_index];
        heap[parent_index] = heap[insert_index];
        heap[insert_index] = swap_helper;

        insert_index = parent_index;
        parent_index = get_parent_index(insert_index);
    }

    heap_usage++;
}

extern BOOL heap_extract_min(BTREE **min_element)
{
    int smaller_child_index;
    int parent_index;
    BTREE *swap_helper;

    if (heap_usage == 0) {
        return FALSE;
    }
    *min_element = heap[0];

    heap[0] = heap[heap_usage - 1];
    heap[heap_usage - 1] = NULL;
    parent_index = 0;

    heap_usage--;

    smaller_child_index = get_smaller_child_index(parent_index);
    while (smaller_child_index != -1
            && (heap[smaller_child_index]->value < heap[parent_index]->value))
    {
        swap_helper = heap[parent_index];
        heap[parent_index] = heap[smaller_child_index];
        heap[smaller_child_index] = swap_helper;

        parent_index = smaller_child_index;
        smaller_child_index = get_smaller_child_index(parent_index);
    }

    check_less_memory();
    return TRUE;
}

extern void heap_print(void)
{
    heap_rec_print(0, 0);
}

static void heap_rec_print(int index, int offset)
{
    int i;
    if (index >= heap_usage)
    {
        return;
    }
    else
    {
        for (i = 0; i < offset; ++i)
        {
            printf(INDENTATION);
        }
        printf("|-- %d", heap[index]->value);
        printf("\n");
    }
    heap_rec_print(index * 2 + 1, offset + 1);
    heap_rec_print(index * 2 + 2, offset + 1);
}

static void expand_heap(void)
{
    heap = realloc(heap, (heap_size + ALLOC_SIZE)*ALLOC_BYTES);
    if (heap == NULL)
    {
        printf(ERR_EXPAND);
        exit(EXIT_FAILURE);
    }
    heap_size += ALLOC_SIZE;
}

static void reduce_heap(void)
{
    heap = realloc(heap, (heap_size - ALLOC_SIZE)*ALLOC_BYTES);
    if (heap == NULL)
    {
        printf(ERR_REDUCE);
        exit(EXIT_FAILURE);
    }
    heap_size -= ALLOC_SIZE;
}

static int get_parent_index(int child_index)
{
    if (child_index == 0)
    {
        return -1;
    }
    else if (is_even(child_index))
    {
        return (child_index - 2) / 2;
    }
    else
    {
        return (child_index - 1) / 2;
    }
}

static int get_smaller_child_index(int parent_index)
{
    if ((parent_index * 2 + 1) >= heap_usage)
    {
        return -1;
    }
    else if (((parent_index * 2 + 2) < heap_usage)
            && (heap[parent_index * 2 + 2]->value < heap[parent_index * 2 + 1]->value))
    {
        return parent_index * 2 + 2;
    }
    else
    {
        return parent_index * 2 + 1;
    }
}

static BOOL is_even(int number)
{
    return !(number & 0x1);
}

static void check_more_memory()
{
    if (heap_usage == heap_size)
    {
        expand_heap();
    }
}

static void check_less_memory()
{
    if (heap_usage <= heap_size - ALLOC_SIZE)
    {
        reduce_heap();
    }
}
